A cryptographic system is a computer system that uses cryptography, typically to secure or authenticate data communication between a pair of computing devices connected to one another through a data communication link in the system. Each computing device has a cryptographic unit with the processing capacity to implement one or more cryptographic protocols used to secure or authenticate the data communication. The cryptographic protocols typically perform arithmetic operations on the bit strings representing parameters, messages, or data in the protocols to produce a bit string representing the output from the protocol.
In cryptographic systems, Certification Authorities (CAs) are trusted 3rd parties responsible for vouching for the authenticity of public keys. For example, if correspondent A wishes to distribute its public key WA, correspondent A may request that a CA issue a certificate for public key WA.
Depending upon the application, the CA may issue an implicit certificate for public key WA. Implicit certificates are known in the art. Unlike conventional “explicit” certificates, implicit certificates require no explicit verification of the CA's signature. Therefore, implicit certificates are generally smaller in size and can offer bandwidth savings over conventional explicit certificates. A public key distributed via such an implicit certificate is implicitly authenticated by successfully using the public key in an operation that requires the use of the corresponding private key.
A well-known implicit certificate scheme is Elliptic Curve Qu-Vanstone (ECQV). This scheme provides implicit authentication when the implicit certificate is used in conjunction with an operation requiring the sender to use the corresponding private key, such, as in ECDH, ECMQV, or ECDSA operations. A summary of ECQV is as follows.
A correspondent, A, wishing to establish a private/public key pair (wA, WA) and distribute public key WA via an implicit certificate, first uses its random number generator to generate a random integer to be used as an ephemeral private key dA. The cryptographic unit then generates a corresponding ephemeral public key QA=dAG, where G is the base point on the underlying elliptic curve and a generator of the subgroup of the elliptic curve group. Correspondent A then sends QA, as well as any identity information, to the CA. The CA receives QA and the identity information and performs the following steps:                1. Verify the received ephemeral public key QA and identity information. Verification can be done a number of ways. For example, the CA may verify that QA is a proper public key that satisfies specific criteria, such as being a point on the underlying, elliptic curve, and/or satisfies defined statistical criteria. In another example, the CA verifies whether the identity information is correct. If verification fails, abort operation. If verification succeeds, proceed.        2. Generate an ephemeral private and public key pair (dCA, QCA), where QCA=dCAG.        3. Compute public key contribution data BA=QA+QCA.        4. Construct certificate data IA.        5. Construct an implicit certificate ICA containing BA and IA.        6. Compute e=Hash(ICA).        7. Compute private key contribution data s=edCA+wCA (mod n), where n is the order of base point. G, and wCA is the static private key of the CA.        8. Send ICA and s to correspondent A.        
Upon receiving ICA and s, correspondent A performs the following steps to calculate its key pair (wA, WA):                1. Operate on ICA to obtain BA and IA.        2. Verify the contents of ICA according to the application rules. For example, this may include verifying the information is properly formatted, verifying content of IA matches information sent by correspondent A to the CA, and/or verifying BA is a valid point on the underlying curve.        3. Compute e=Hash(ICA) and verify e≠0.        4. Compute its private key wA=edA+s (mod n).        5. Compute its public key WA=eBA+WCA, where WCA is the static public key of the CA corresponding to the static private key wCA.        
The CA distributes the implicit certificate ICA to the other correspondents. A particular correspondent, say correspondent B, receives ICA and derives the public key WA of correspondent A as follows:                1. Operate on ICA to compute BA and IA;        2. Verify the contents of ICA according to the application rules;        3. Compute e=Hash(ICA) and verify e≠0; and        4. Compute public key WA=eBA+WCA.        
Correspondent B is therefore able to use the static public key WCA of the CA to derive WA from the implicit certificate ICA. However, correspondent B has no way of knowing whether correspondent A possesses the corresponding private key wA. This is also the case with ordinary explicit certificates (e.g. ECDSA and RSA certificates), unless the CA first wants proof of possession before issuing a certificate. Therefore, authentication of correspondent A and its public key WA is not complete until an operation involving both WA and wA is successfully performed. For example, correspondent A and correspondent B may subsequently engage in an ECMQV key agreement or ECDSA signature protocol, both of which require the use of WA and wA. If the key agreement or signature operations fail, then WA might not have been authentic or valid. On the other hand, if the key agreement or signature operations are successful; then correspondent A must possess wA, and the authenticity and validity of WA is implicitly verified.
The ECQV implicit certificate scheme above is an example of an implicit certificate scheme. It is generally desired to reduce the number of computations performed in an implicit certificate scheme.